package com.breeze.leetcode;

/**
 * https://leetcode-cn.com/problems/maximum-product-subarray/
 * 152. 乘积最大子数组
 * 给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
 */
public class LeetCode152 {
    /**
     * 1. 动态规划
     * -> 状态定义：dp为大小为n的数组，dp[i] 来表示[0,i]数组的连续子数组最大乘积
     * -> 状态转移方程
     * 1. dp[i] = max(dp[i-1],与nums[i]连续的最大值), (i>0)
     * 2. dp[i] = nums[i] (i=0)
     * -> 初始值：dp初始化，默认值为0即符合
     * -> 返回值：dp[i]
     * <p>
     * 注意：由于与nums[i]连续的最大值还是用了一次for循环，导致性能降低，也导致原数组无法了i用，从而需要新的dp数组保存。该算法在通过LeetCode测试时也是垫底的水平
     * 时间复杂度O(n^2)
     * 空间复杂度:O(n)
     */
    public int maxProduct(int[] nums) {
        int[] dp = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            if (i == 0) {
                dp[i] = nums[i];
            } else {
                int max = nums[i];
                int temp = nums[i];
                for (int j = i - 1; j >= 0; j--) {
                    temp *= nums[j];
                    max = Math.max(max, temp);
                }
                dp[i] = Math.max(dp[i - 1], max);
            }
        }
        return dp[nums.length - 1];
    }

    /**
     * 2. 动态规划 优化版
     * 着重对与nums[i]连续的最大值的改善
     * <p>
     * 观察数相乘的特性：正整数相乘会增大，与负数相乘变为最小，再相乘一个负数又会变为最大。故在状态转移时需要同时记录当前最大值和最小值。
     */
    public int maxProduct1(int[] nums) {
        int curMax = 1, curMin = 1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0) {
                int temp = curMax;
                curMax = curMin;
                curMin = temp;
            }
            curMax = Math.max(curMax * nums[i], nums[i]);
            curMin = Math.min(curMin * nums[i], nums[i]);
            if (i == 0) continue;
            nums[i] = Math.max(nums[i - 1], curMax);
        }
        return nums[nums.length - 1];
    }


    public static void main(String[] args) {
        LeetCode152 leetCode152 = new LeetCode152();
        int[] nums = new int[]{-2, 3, -4};
        int res = leetCode152.maxProduct1(nums);
        System.out.println("res = " + res);
    }
}
